This invention relates to data processing and, more particularly, to processing of data having a quadtree topology.
The quadtree is a data structure that is widely used in image processing, computer graphics, data compression, and other applications. The quadtree can be viewed as a tree in which each node has at most four children. FIG. 1 illustrates an image where each picture area can be divided into four parts, and each resulting area can be recursively divided to thus yield areas of, effectively, any desired small size. It should be kept in mind that although the following discussion illustratively speaks in terms of an image, which is a 2-dimensional object, the principles disclosed herein apply to a much broader range of useful applications.
To efficiently process the FIG. 1 image, it might be advantageous to subdivide the image into large areas in portions of the image that change little, and to subdivide the image into small areas in portions of the image that change a lot. The same situation exists in topographical rendering problems, where the topography of a three-dimensional surface (e.g., a hill, a face, a dress) is represented in triangles, and each node of the quadtree stores 8 triangle surfaces oriented in 3-D space.
In processing data that is represented in a quadtree data structure and stored in memory, it is often necessary to traverse the quadtree. Traversing from a child node to the immediately previous parent node is quite simple. Traversing from a child node to an earlier ancestor node is slightly more difficult and more time consuming, but still quite easy. Traversing from some arbitrary node at some level to another arbitrary node in another level, where there is no direct connection between the nodes except by traversing a number of levels up the quadtree, can become quite time consuming. To move to a same-level neighbor in the quadtree can actually require the use of significant processing resources just to find out how to reach that neighbor node (i.e., how high up the tree one needs to traverse, and which branches down one must select).
Prior art attempts at solving this problem are reported on by a number of researchers. In xe2x80x9cFinding neighbors of equal size in linear quadtrees and octrees in constant time,xe2x80x9d CVGIP: Image Understanding, 55(3):221-230, May 1992, G. Schrack shows how to travel between neighbor nodes in the quadtree (located at the same level). However, the Schrack method is limited to accessing neighbor nodes. In xe2x80x9cNavigating through meshes implemented as linear quadtrees,xe2x80x9d Technical Report, Computer Science Dept., Center for Automation Research, University of Maryland, CS-TR-3900, April, 1998, Samet et al show how to store a particular class of triangulations in a quadtree and how to assign to each triangle a binary index (vector of 0""s and 1""s) so that neighbor triangles at the same level and neighbors located at a different level can be accessed in constant time. However, the Semet et al method implies storing an explicit index in each quadtree node, which increases the storage requirements and exacerbates what is a critical issue with a linear quadtree.
Further, both works restrict the quadtree traversal to neighbor nodes. Thus, the known art has not solved the general problem of efficiently traversing from one node to any other arbitrary node.
The deficiencies in the prior art are overcome and a technical advance is realized with a simple, algorithmic, indexing of the quadtree nodes. The indexing is arranged to insure that the index value of a node in column i and row j differs from the index value of a node in row k and column i by a value that is constant, regardless of the value of row j. Similarly, the index value of a node in row j and column i differs from the index value of a node in row k and column i by a value that is a constant, regardless of the value of column i. With such an arrangement, no indexing information, or pointer information, needs to be stored. Moreover, traversal from any node to any other node can be accomplished with a single calculation followed by a single traversal which, in the context of this disclosure, is considered to be a single step.